// Copyright 2023 The Chromium Authors
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "components/browsing_topics/common/semantic_tree.h"

#include "components/strings/grit/components_strings.h"

namespace browsing_topics {

namespace {

const uint16_t kChildToParent[] = {
    0,   1,   1,   1,   1,   1,   1,   7,   1,   1,   1,   1,   12,  12,  12,
    12,  12,  12,  12,  12,  12,  12,  1,   23,  23,  23,  23,  23,  23,  23,
    23,  23,  23,  33,  33,  33,  23,  23,  23,  23,  40,  1,   1,   1,   1,
    45,  45,  45,  48,  45,  45,  45,  1,   53,  53,  53,  0,   57,  57,  57,
    57,  57,  62,  62,  62,  62,  62,  62,  62,  62,  62,  62,  62,  62,  62,
    62,  76,  62,  57,  57,  57,  57,  57,  83,  57,  0,   86,  86,  88,  88,
    88,  88,  88,  88,  88,  86,  86,  97,  86,  0,   100, 100, 0,   103, 104,
    103, 106, 103, 103, 103, 110, 110, 103, 103, 114, 103, 103, 117, 103, 103,
    103, 103, 103, 103, 103, 0,   126, 126, 126, 129, 129, 129, 129, 126, 126,
    126, 126, 137, 126, 126, 140, 140, 140, 140, 140, 140, 140, 140, 0,   149,
    150, 149, 149, 153, 149, 155, 149, 149, 158, 158, 158, 158, 158, 149, 164,
    164, 164, 164, 164, 149, 149, 0,   172, 173, 173, 175, 176, 173, 172, 0,
    180, 180, 180, 183, 183, 183, 183, 183, 183, 183, 183, 183, 180, 180, 180,
    0,   196, 196, 196, 196, 196, 201, 201, 196, 196, 196, 0,   207, 207, 207,
    207, 207, 207, 207, 0,   215, 215, 215, 215, 215, 215, 215, 215, 215, 215,
    0,   226, 227, 227, 227, 227, 231, 227, 227, 227, 226, 236, 236, 0,   239,
    239, 241, 0,   243, 243, 243, 243, 243, 243, 0,   250, 250, 250, 0,   254,
    255, 255, 255, 258, 258, 258, 254, 0,   263, 263, 265, 265, 265, 265, 265,
    263, 0,   272, 272, 0,   275, 275, 275, 0,   279, 279, 281, 279, 279, 279,
    279, 279, 279, 0,   289, 289, 289, 292, 289, 289, 289, 289, 289, 0,   299,
    299, 299, 299, 299, 299, 299, 299, 299, 299, 299, 299, 299, 312, 299, 299,
    299, 299, 299, 299, 299, 299, 299, 299, 299, 299, 299, 299, 299, 299, 299,
    299, 0,   332, 332, 332, 332, 332, 332, 332, 332, 332, 332, 332, 332, 344,
    344, 344, 344, 332,
};

constexpr size_t kNumTopics = std::size(kChildToParent);
constexpr Topic kNullTopic = Topic(0);

static_assert(kNumTopics == 349);
static_assert(IDS_PRIVACY_SANDBOX_TOPICS_TAXONOMY_V1_TOPIC_ID_349 -
                  IDS_PRIVACY_SANDBOX_TOPICS_TAXONOMY_V1_TOPIC_ID_1 + 1 ==
              kNumTopics);
// These asserts also have a side-effect of preventing unused resource
// removal from removing them.
#define ASSERT_RESOURCE_ID(num)                                              \
  static_assert(IDS_PRIVACY_SANDBOX_TOPICS_TAXONOMY_V1_TOPIC_ID_##num -      \
                    IDS_PRIVACY_SANDBOX_TOPICS_TAXONOMY_V1_TOPIC_ID_1 + 1 == \
                num)
ASSERT_RESOURCE_ID(2);
ASSERT_RESOURCE_ID(3);
ASSERT_RESOURCE_ID(4);
ASSERT_RESOURCE_ID(5);
ASSERT_RESOURCE_ID(6);
ASSERT_RESOURCE_ID(7);
ASSERT_RESOURCE_ID(8);
ASSERT_RESOURCE_ID(9);
ASSERT_RESOURCE_ID(10);
ASSERT_RESOURCE_ID(11);
ASSERT_RESOURCE_ID(12);
ASSERT_RESOURCE_ID(13);
ASSERT_RESOURCE_ID(14);
ASSERT_RESOURCE_ID(15);
ASSERT_RESOURCE_ID(16);
ASSERT_RESOURCE_ID(17);
ASSERT_RESOURCE_ID(18);
ASSERT_RESOURCE_ID(19);
ASSERT_RESOURCE_ID(20);
ASSERT_RESOURCE_ID(21);
ASSERT_RESOURCE_ID(22);
ASSERT_RESOURCE_ID(23);
ASSERT_RESOURCE_ID(24);
ASSERT_RESOURCE_ID(25);
ASSERT_RESOURCE_ID(26);
ASSERT_RESOURCE_ID(27);
ASSERT_RESOURCE_ID(28);
ASSERT_RESOURCE_ID(29);
ASSERT_RESOURCE_ID(30);
ASSERT_RESOURCE_ID(31);
ASSERT_RESOURCE_ID(32);
ASSERT_RESOURCE_ID(33);
ASSERT_RESOURCE_ID(34);
ASSERT_RESOURCE_ID(35);
ASSERT_RESOURCE_ID(36);
ASSERT_RESOURCE_ID(37);
ASSERT_RESOURCE_ID(38);
ASSERT_RESOURCE_ID(39);
ASSERT_RESOURCE_ID(40);
ASSERT_RESOURCE_ID(41);
ASSERT_RESOURCE_ID(42);
ASSERT_RESOURCE_ID(43);
ASSERT_RESOURCE_ID(44);
ASSERT_RESOURCE_ID(45);
ASSERT_RESOURCE_ID(46);
ASSERT_RESOURCE_ID(47);
ASSERT_RESOURCE_ID(48);
ASSERT_RESOURCE_ID(49);
ASSERT_RESOURCE_ID(50);
ASSERT_RESOURCE_ID(51);
ASSERT_RESOURCE_ID(52);
ASSERT_RESOURCE_ID(53);
ASSERT_RESOURCE_ID(54);
ASSERT_RESOURCE_ID(55);
ASSERT_RESOURCE_ID(56);
ASSERT_RESOURCE_ID(57);
ASSERT_RESOURCE_ID(58);
ASSERT_RESOURCE_ID(59);
ASSERT_RESOURCE_ID(60);
ASSERT_RESOURCE_ID(61);
ASSERT_RESOURCE_ID(62);
ASSERT_RESOURCE_ID(63);
ASSERT_RESOURCE_ID(64);
ASSERT_RESOURCE_ID(65);
ASSERT_RESOURCE_ID(66);
ASSERT_RESOURCE_ID(67);
ASSERT_RESOURCE_ID(68);
ASSERT_RESOURCE_ID(69);
ASSERT_RESOURCE_ID(70);
ASSERT_RESOURCE_ID(71);
ASSERT_RESOURCE_ID(72);
ASSERT_RESOURCE_ID(73);
ASSERT_RESOURCE_ID(74);
ASSERT_RESOURCE_ID(75);
ASSERT_RESOURCE_ID(76);
ASSERT_RESOURCE_ID(77);
ASSERT_RESOURCE_ID(78);
ASSERT_RESOURCE_ID(79);
ASSERT_RESOURCE_ID(80);
ASSERT_RESOURCE_ID(81);
ASSERT_RESOURCE_ID(82);
ASSERT_RESOURCE_ID(83);
ASSERT_RESOURCE_ID(84);
ASSERT_RESOURCE_ID(85);
ASSERT_RESOURCE_ID(86);
ASSERT_RESOURCE_ID(87);
ASSERT_RESOURCE_ID(88);
ASSERT_RESOURCE_ID(89);
ASSERT_RESOURCE_ID(90);
ASSERT_RESOURCE_ID(91);
ASSERT_RESOURCE_ID(92);
ASSERT_RESOURCE_ID(93);
ASSERT_RESOURCE_ID(94);
ASSERT_RESOURCE_ID(95);
ASSERT_RESOURCE_ID(96);
ASSERT_RESOURCE_ID(97);
ASSERT_RESOURCE_ID(98);
ASSERT_RESOURCE_ID(99);
ASSERT_RESOURCE_ID(100);
ASSERT_RESOURCE_ID(101);
ASSERT_RESOURCE_ID(102);
ASSERT_RESOURCE_ID(103);
ASSERT_RESOURCE_ID(104);
ASSERT_RESOURCE_ID(105);
ASSERT_RESOURCE_ID(106);
ASSERT_RESOURCE_ID(107);
ASSERT_RESOURCE_ID(108);
ASSERT_RESOURCE_ID(109);
ASSERT_RESOURCE_ID(110);
ASSERT_RESOURCE_ID(111);
ASSERT_RESOURCE_ID(112);
ASSERT_RESOURCE_ID(113);
ASSERT_RESOURCE_ID(114);
ASSERT_RESOURCE_ID(115);
ASSERT_RESOURCE_ID(116);
ASSERT_RESOURCE_ID(117);
ASSERT_RESOURCE_ID(118);
ASSERT_RESOURCE_ID(119);
ASSERT_RESOURCE_ID(120);
ASSERT_RESOURCE_ID(121);
ASSERT_RESOURCE_ID(122);
ASSERT_RESOURCE_ID(123);
ASSERT_RESOURCE_ID(124);
ASSERT_RESOURCE_ID(125);
ASSERT_RESOURCE_ID(126);
ASSERT_RESOURCE_ID(127);
ASSERT_RESOURCE_ID(128);
ASSERT_RESOURCE_ID(129);
ASSERT_RESOURCE_ID(130);
ASSERT_RESOURCE_ID(131);
ASSERT_RESOURCE_ID(132);
ASSERT_RESOURCE_ID(133);
ASSERT_RESOURCE_ID(134);
ASSERT_RESOURCE_ID(135);
ASSERT_RESOURCE_ID(136);
ASSERT_RESOURCE_ID(137);
ASSERT_RESOURCE_ID(138);
ASSERT_RESOURCE_ID(139);
ASSERT_RESOURCE_ID(140);
ASSERT_RESOURCE_ID(141);
ASSERT_RESOURCE_ID(142);
ASSERT_RESOURCE_ID(143);
ASSERT_RESOURCE_ID(144);
ASSERT_RESOURCE_ID(145);
ASSERT_RESOURCE_ID(146);
ASSERT_RESOURCE_ID(147);
ASSERT_RESOURCE_ID(148);
ASSERT_RESOURCE_ID(149);
ASSERT_RESOURCE_ID(150);
ASSERT_RESOURCE_ID(151);
ASSERT_RESOURCE_ID(152);
ASSERT_RESOURCE_ID(153);
ASSERT_RESOURCE_ID(154);
ASSERT_RESOURCE_ID(155);
ASSERT_RESOURCE_ID(156);
ASSERT_RESOURCE_ID(157);
ASSERT_RESOURCE_ID(158);
ASSERT_RESOURCE_ID(159);
ASSERT_RESOURCE_ID(160);
ASSERT_RESOURCE_ID(161);
ASSERT_RESOURCE_ID(162);
ASSERT_RESOURCE_ID(163);
ASSERT_RESOURCE_ID(164);
ASSERT_RESOURCE_ID(165);
ASSERT_RESOURCE_ID(166);
ASSERT_RESOURCE_ID(167);
ASSERT_RESOURCE_ID(168);
ASSERT_RESOURCE_ID(169);
ASSERT_RESOURCE_ID(170);
ASSERT_RESOURCE_ID(171);
ASSERT_RESOURCE_ID(172);
ASSERT_RESOURCE_ID(173);
ASSERT_RESOURCE_ID(174);
ASSERT_RESOURCE_ID(175);
ASSERT_RESOURCE_ID(176);
ASSERT_RESOURCE_ID(177);
ASSERT_RESOURCE_ID(178);
ASSERT_RESOURCE_ID(179);
ASSERT_RESOURCE_ID(180);
ASSERT_RESOURCE_ID(181);
ASSERT_RESOURCE_ID(182);
ASSERT_RESOURCE_ID(183);
ASSERT_RESOURCE_ID(184);
ASSERT_RESOURCE_ID(185);
ASSERT_RESOURCE_ID(186);
ASSERT_RESOURCE_ID(187);
ASSERT_RESOURCE_ID(188);
ASSERT_RESOURCE_ID(189);
ASSERT_RESOURCE_ID(190);
ASSERT_RESOURCE_ID(191);
ASSERT_RESOURCE_ID(192);
ASSERT_RESOURCE_ID(193);
ASSERT_RESOURCE_ID(194);
ASSERT_RESOURCE_ID(195);
ASSERT_RESOURCE_ID(196);
ASSERT_RESOURCE_ID(197);
ASSERT_RESOURCE_ID(198);
ASSERT_RESOURCE_ID(199);
ASSERT_RESOURCE_ID(200);
ASSERT_RESOURCE_ID(201);
ASSERT_RESOURCE_ID(202);
ASSERT_RESOURCE_ID(203);
ASSERT_RESOURCE_ID(204);
ASSERT_RESOURCE_ID(205);
ASSERT_RESOURCE_ID(206);
ASSERT_RESOURCE_ID(207);
ASSERT_RESOURCE_ID(208);
ASSERT_RESOURCE_ID(209);
ASSERT_RESOURCE_ID(210);
ASSERT_RESOURCE_ID(211);
ASSERT_RESOURCE_ID(212);
ASSERT_RESOURCE_ID(213);
ASSERT_RESOURCE_ID(214);
ASSERT_RESOURCE_ID(215);
ASSERT_RESOURCE_ID(216);
ASSERT_RESOURCE_ID(217);
ASSERT_RESOURCE_ID(218);
ASSERT_RESOURCE_ID(219);
ASSERT_RESOURCE_ID(220);
ASSERT_RESOURCE_ID(221);
ASSERT_RESOURCE_ID(222);
ASSERT_RESOURCE_ID(223);
ASSERT_RESOURCE_ID(224);
ASSERT_RESOURCE_ID(225);
ASSERT_RESOURCE_ID(226);
ASSERT_RESOURCE_ID(227);
ASSERT_RESOURCE_ID(228);
ASSERT_RESOURCE_ID(229);
ASSERT_RESOURCE_ID(230);
ASSERT_RESOURCE_ID(231);
ASSERT_RESOURCE_ID(232);
ASSERT_RESOURCE_ID(233);
ASSERT_RESOURCE_ID(234);
ASSERT_RESOURCE_ID(235);
ASSERT_RESOURCE_ID(236);
ASSERT_RESOURCE_ID(237);
ASSERT_RESOURCE_ID(238);
ASSERT_RESOURCE_ID(239);
ASSERT_RESOURCE_ID(240);
ASSERT_RESOURCE_ID(241);
ASSERT_RESOURCE_ID(242);
ASSERT_RESOURCE_ID(243);
ASSERT_RESOURCE_ID(244);
ASSERT_RESOURCE_ID(245);
ASSERT_RESOURCE_ID(246);
ASSERT_RESOURCE_ID(247);
ASSERT_RESOURCE_ID(248);
ASSERT_RESOURCE_ID(249);
ASSERT_RESOURCE_ID(250);
ASSERT_RESOURCE_ID(251);
ASSERT_RESOURCE_ID(252);
ASSERT_RESOURCE_ID(253);
ASSERT_RESOURCE_ID(254);
ASSERT_RESOURCE_ID(255);
ASSERT_RESOURCE_ID(256);
ASSERT_RESOURCE_ID(257);
ASSERT_RESOURCE_ID(258);
ASSERT_RESOURCE_ID(259);
ASSERT_RESOURCE_ID(260);
ASSERT_RESOURCE_ID(261);
ASSERT_RESOURCE_ID(262);
ASSERT_RESOURCE_ID(263);
ASSERT_RESOURCE_ID(264);
ASSERT_RESOURCE_ID(265);
ASSERT_RESOURCE_ID(266);
ASSERT_RESOURCE_ID(267);
ASSERT_RESOURCE_ID(268);
ASSERT_RESOURCE_ID(269);
ASSERT_RESOURCE_ID(270);
ASSERT_RESOURCE_ID(271);
ASSERT_RESOURCE_ID(272);
ASSERT_RESOURCE_ID(273);
ASSERT_RESOURCE_ID(274);
ASSERT_RESOURCE_ID(275);
ASSERT_RESOURCE_ID(276);
ASSERT_RESOURCE_ID(277);
ASSERT_RESOURCE_ID(278);
ASSERT_RESOURCE_ID(279);
ASSERT_RESOURCE_ID(280);
ASSERT_RESOURCE_ID(281);
ASSERT_RESOURCE_ID(282);
ASSERT_RESOURCE_ID(283);
ASSERT_RESOURCE_ID(284);
ASSERT_RESOURCE_ID(285);
ASSERT_RESOURCE_ID(286);
ASSERT_RESOURCE_ID(287);
ASSERT_RESOURCE_ID(288);
ASSERT_RESOURCE_ID(289);
ASSERT_RESOURCE_ID(290);
ASSERT_RESOURCE_ID(291);
ASSERT_RESOURCE_ID(292);
ASSERT_RESOURCE_ID(293);
ASSERT_RESOURCE_ID(294);
ASSERT_RESOURCE_ID(295);
ASSERT_RESOURCE_ID(296);
ASSERT_RESOURCE_ID(297);
ASSERT_RESOURCE_ID(298);
ASSERT_RESOURCE_ID(299);
ASSERT_RESOURCE_ID(300);
ASSERT_RESOURCE_ID(301);
ASSERT_RESOURCE_ID(302);
ASSERT_RESOURCE_ID(303);
ASSERT_RESOURCE_ID(304);
ASSERT_RESOURCE_ID(305);
ASSERT_RESOURCE_ID(306);
ASSERT_RESOURCE_ID(307);
ASSERT_RESOURCE_ID(308);
ASSERT_RESOURCE_ID(309);
ASSERT_RESOURCE_ID(310);
ASSERT_RESOURCE_ID(311);
ASSERT_RESOURCE_ID(312);
ASSERT_RESOURCE_ID(313);
ASSERT_RESOURCE_ID(314);
ASSERT_RESOURCE_ID(315);
ASSERT_RESOURCE_ID(316);
ASSERT_RESOURCE_ID(317);
ASSERT_RESOURCE_ID(318);
ASSERT_RESOURCE_ID(319);
ASSERT_RESOURCE_ID(320);
ASSERT_RESOURCE_ID(321);
ASSERT_RESOURCE_ID(322);
ASSERT_RESOURCE_ID(323);
ASSERT_RESOURCE_ID(324);
ASSERT_RESOURCE_ID(325);
ASSERT_RESOURCE_ID(326);
ASSERT_RESOURCE_ID(327);
ASSERT_RESOURCE_ID(328);
ASSERT_RESOURCE_ID(329);
ASSERT_RESOURCE_ID(330);
ASSERT_RESOURCE_ID(331);
ASSERT_RESOURCE_ID(332);
ASSERT_RESOURCE_ID(333);
ASSERT_RESOURCE_ID(334);
ASSERT_RESOURCE_ID(335);
ASSERT_RESOURCE_ID(336);
ASSERT_RESOURCE_ID(337);
ASSERT_RESOURCE_ID(338);
ASSERT_RESOURCE_ID(339);
ASSERT_RESOURCE_ID(340);
ASSERT_RESOURCE_ID(341);
ASSERT_RESOURCE_ID(342);
ASSERT_RESOURCE_ID(343);
ASSERT_RESOURCE_ID(344);
ASSERT_RESOURCE_ID(345);
ASSERT_RESOURCE_ID(346);
ASSERT_RESOURCE_ID(347);
ASSERT_RESOURCE_ID(348);
ASSERT_RESOURCE_ID(349);

bool IsTopicValid(Topic topic) {
  int i = static_cast<int>(topic);
  return i > 0 && i <= static_cast<int>(kNumTopics);
}

Topic GetParentTopic(Topic topic) {
  return Topic(kChildToParent[static_cast<int>(topic) - 1]);
}

bool IsAncestorTopic(Topic src, Topic target) {
  while (src != kNullTopic) {
    src = GetParentTopic(src);
    if (src == target) {
      return true;
    }
  }
  return false;
}
}  // namespace

SemanticTree::SemanticTree() = default;
SemanticTree::~SemanticTree() = default;

std::vector<Topic> SemanticTree::GetDescendantTopics(const Topic& topic) {
  std::vector<Topic> ret;
  for (size_t i = 0; i < kNumTopics; ++i) {
    Topic cur_topic = Topic(i + 1);
    if (IsAncestorTopic(cur_topic, topic)) {
      ret.push_back(cur_topic);
    }
  }
  return ret;
}

std::vector<Topic> SemanticTree::GetAncestorTopics(const Topic& topic) {
  std::vector<Topic> ancestor_topics;

  if (IsTopicValid(topic)) {
    Topic cur_topic = GetParentTopic(topic);
    while (cur_topic != kNullTopic) {
      ancestor_topics.push_back(cur_topic);
      cur_topic = GetParentTopic(cur_topic);
    }
  }
  return ancestor_topics;
}

absl::optional<int> SemanticTree::GetLocalizedNameMessageId(
    const Topic& topic,
    int taxonomy_version) {
  if (!IsTopicValid(topic) || taxonomy_version != 1) {
    return absl::nullopt;
  }
  return IDS_PRIVACY_SANDBOX_TOPICS_TAXONOMY_V1_TOPIC_ID_1 +
         static_cast<int>(topic) - 1;
}

}  // namespace browsing_topics
